#include <stdio.h>
#include <string.h>

#define MAXINT 9999
int arr[100][100] = {0};
int opperformed[100][100] = {0};

enum costs {
	MOVE_COST = 0,
	REPLACE_COST = 4,
	INSERT_COST = 3,
	DELETE_COST = 2
};

enum opers {
	MOVE,
	REPLACE,
	INSERT,
	DELETE
};

char *op_strs[] = {
	"Move",
	"Replace",
	"Insert",
	"Delete"
};

int opstack[100];
int top = 0;


void print_arr(int m, int n)
{
	int i,j;

	for (i = 0; i < m; i++) {
		for (j = 0; j < n; j++)
			printf("%4d ", arr[i][j]);
		printf("\n");
	}
	printf("\n");
}


int min(int a, int b)
{
	return (a < b) ? a : b;
}

int retrace(int m, int n)
{
	int i = m - 1, j = n - 1;

	while (i > 0 || j > 0) {
		opstack[top++] = opperformed[i][j];

		switch(opperformed[i][j]) {
		case REPLACE:
		case MOVE:
			i--;
			j--;
			break;

		case INSERT:
			j--;
			break;

		case DELETE:
			i--;
			break;

		default:
			printf("Unknown op: %d at (%d, %d)\n", opperformed[i][j], i, j);
			break;
		}
	}
}


void print_seq(char *source, char *dest)
{
	int i = 0, j = 0;
	int m = strlen(source);
	char out_str[100] = "*";
	strcat(out_str, source);

	printf("Initial: %s\n", out_str);

	while (top > 0) {
		switch(opstack[--top]) {
		case REPLACE:
			out_str[i++] = dest[j++];
			out_str[i] = '*';
			break;

		case MOVE:
			out_str[i] = out_str[i+1];
			out_str[++i] = '*';
			j++;
			break;

		case INSERT: {
			int x;
			out_str[i++] = dest[j++];
			m++;
			for (x = m; x > i; x--)
				out_str[x] = out_str[x - 1];
			out_str[i] = '*';
		}
			break;

		case DELETE: {
			int x;
			for (x = i + 1; x < m; x++)
				out_str[x] = out_str[x + 1];
			out_str[m--] = 0;
		}
			break;

		default:
			printf("Unknown op: %d at (%d, %d)\n", opperformed[i][j], i, j);
			break;
		}

		printf("%s: ", op_strs[opstack[top]]);
		printf("%s\n", out_str);
	}
}



int main(int argc, char **argv)
{
	int i, j;

	char source[100] = "_algorithm";
	char dest[100] = "_analysis";
	int m = strlen(source);
	int n = strlen(dest);

	printf("source: %d dest: %d\n", m, n);

	for (i = 1; i < m; i++) {
		arr[i][0] = arr[i - 1][0] + DELETE_COST;
		opperformed[i][0] = DELETE;
	}

	for (j = 1; j < n; j++) {
		arr[0][j] = arr[0][j - 1] + INSERT_COST;
		opperformed[0][j - 1] = INSERT;
	}

	for (i = 1; i < m; i++) {
		for(j = 1; j < n; j++) {
			int op = MOVE;
			int mcost = (source[i] == dest[j]) ? arr[i - 1][j - 1] : MAXINT;
			int mincost = mcost;

			int rcost = arr[i - 1][j - 1] + REPLACE_COST;
			if (rcost < mincost) {
				mincost = rcost;
				op = REPLACE;
			}

			int icost = arr[i][j - 1] + INSERT_COST;
			if (icost < mincost) {
				mincost = icost;
				op = INSERT;
			}

			int dcost = arr[i - 1][j] + DELETE_COST;
			if (dcost < mincost) {
				mincost = dcost;
				op = DELETE;
			}

			arr[i][j] = mincost;
			opperformed[i][j] = op;
		}
	}

	print_arr(m, n);
	retrace(m, n);
	print_seq(source + 1, dest + 1);

	printf("Total cost: %d\n", arr[m - 1][n - 1]);
	return 0;
}


